class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }

public class Partition {
    public ListNode partition(ListNode head,int x){
        if(head==null){
            return null;
        }
        //设定before链表存储比x值小的节点，包括bs头节点引用和be尾节点引用
        ListNode bs=null;
        ListNode be=null;
        //设定after链表存储不比x值小的节点，包括as头节点引用和ae尾节点引用
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=head;
        while(cur!=null) {
            if (cur.val < x) {
                //判断是否为第一次插入
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }else{
                //判断是否为第一次插入
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        //处理全部都不小于x值的情况
        if(bs==null){
            return as;
        }
        //ae.next设定为空，避免成环
        if(as!=null){
            ae.next=null;
        }
        //合并两链表
        be.next=as;
        return bs;
    }
}